# sage.doctest: needs sage.libs.gap
r"""
Pieri Factors
"""
# ****************************************************************************
#  Copyright (C) 2009-2010 Steven Pon <spon at math.ucdavis.edu>
#                          Anne Schilling < anne at math.ucdavis.edu>
#                          Nicolas M. Thiery <nthiery at users.sf.net>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#                  https://www.gnu.org/licenses/
# *****************************************************************************

from sage.misc.cachefunc import cached_method
from sage.misc.constant_function import ConstantFunction
from sage.misc.call import attrcall
from sage.misc.lazy_import import lazy_import
from sage.misc.misc_c import prod
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
from sage.structure.parent import Parent
from sage.structure.unique_representation import UniqueRepresentation
from sage.rings.integer import Integer
from sage.rings.rational_field import QQ
from sage.rings.infinity import infinity
from sage.arith.misc import binomial
import sage.combinat.ranker
from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet
from sage.combinat.root_system.root_system import RootSystem
from sage.combinat.root_system.weyl_group import WeylGroup

lazy_import('sage.graphs.digraph', 'DiGraph')
lazy_import('sage.combinat.root_system.dynkin_diagram', 'DynkinDiagram')


class PieriFactors(UniqueRepresentation, Parent):
    r"""
    An abstract class for sets of Pieri factors, used for constructing
    Stanley symmetric functions. The set of Pieri factors for a given
    type can be realized as an order ideal of the Bruhat order poset
    generated by a certain set of maximal elements.

    .. SEEALSO::

        - :meth:`WeylGroups.ParentMethods.pieri_factors`
        - :meth:`WeylGroups.ElementMethods.stanley_symmetric_function`

    EXAMPLES::

        sage: W = WeylGroup(['A',4])
        sage: PF = W.pieri_factors()
        sage: PF.an_element().reduced_word()
        [4, 3, 2, 1]
        sage: Waff = WeylGroup(['A',4,1])
        sage: PFaff = Waff.pieri_factors()
        sage: Waff.from_reduced_word(PF.an_element().reduced_word()) in PFaff
        True

        sage: W = WeylGroup(['B',3,1])
        sage: PF = W.pieri_factors()
        sage: W.from_reduced_word([2,3,2]) in PF.elements()
        True
        sage: PF.cardinality()
        47

        sage: W = WeylGroup(['C',3,1])
        sage: PF = W.pieri_factors()
        sage: PF.generating_series()
        6*z^6 + 14*z^5 + 18*z^4 + 15*z^3 + 9*z^2 + 4*z + 1
        sage: sorted(w.reduced_word() for w in PF if w.length() == 2)
        [[0, 1], [1, 0], [1, 2], [2, 0], [2, 1],
        [2, 3], [3, 0], [3, 1], [3, 2]]

    REFERENCES:

    - [FoSta1994]_
    - [BH1994]_
    - [Lam1996]_
    - [Lam2008]_
    - [LSS2009]_
    - [Pon2010]_
    """

    def _repr_(self):
        r"""
        String representation.

        EXAMPLES::

            sage: WeylGroup(["A", 2, 1]).pieri_factors() # indirect doctest
            Pieri factors for Weyl Group of type ['A', 2, 1] (as a matrix group acting on the root space)
        """
        return "Pieri factors for %s" % self.W

    def __contains__(self, w):
        r"""
        Test for containment.

        EXAMPLES::

            sage: W = WeylGroup(['C',3,1])
            sage: w = W.from_reduced_word([3,2,1,0])
            sage: PF = W.pieri_factors()
            sage: w in PF
            True
            sage: w = W.from_reduced_word([1,0,1])
            sage: w in PF
            True
            sage: w = W.from_reduced_word([1,0,1,0])
            sage: w in PF
            False
            sage: w = W.from_reduced_word([0,1,2,3,2,1,0])
            sage: w in PF
            False
            sage: w = W.from_reduced_word([2,0,3,2,1])
            sage: w in PF
            True

            sage: W = WeylGroup(['B',4,1])
            sage: PF = W.pieri_factors()
            sage: w = W.from_reduced_word([1,2,4,3,1])
            sage: w in PF
            True
            sage: w = W.from_reduced_word([1,2,4,3,1,0])
            sage: w in PF
            False
            sage: w = W.from_reduced_word([2,3,4,3,2,1,0])
            sage: w in PF
            True

            sage: W = WeylGroup(['A',4])
            sage: PF = W.pieri_factors()
            sage: W.from_reduced_word([4,3,1]) in PF
            True
            sage: W.from_reduced_word([1,2]) in PF
            False
        """
        if w not in self.W:
            return False
        return any(w.bruhat_le(m) for m in self.maximal_elements())

    @cached_method
    def elements(self):
        r"""
        Return the elements of ``self``.

        Those are constructed as the elements below the maximal
        elements of ``self`` in Bruhat order.

        OUTPUT: a :class:`RecursivelyEnumeratedSet_generic` object

        EXAMPLES::

            sage: PF = WeylGroup(['A',3]).pieri_factors()
            sage: sorted(w.reduced_word() for w in PF.elements())
            [[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]]

        .. SEEALSO:: :meth:`maximal_elements`

        .. TODO::

            Possibly remove this method and instead have this class
            inherit from :class:`RecursivelyEnumeratedSet_generic`.
        """
        return RecursivelyEnumeratedSet(self.maximal_elements(),
                attrcall('bruhat_lower_covers'), structure=None,
                enumeration='naive')

    def __iter__(self):
        r"""
        Return an iterator over the elements of ``self``.

        EXAMPLES::

            sage: PF = WeylGroup(['A',3,1]).pieri_factors()
            sage: f = PF.__iter__()
            sage: [next(f).reduced_word() for i in range(5)]
            [[], [0], [1], [2], [3]]
        """
        return iter(self.elements())

    def generating_series(self, weight=None):
        r"""
        Return a length generating series for the elements of ``self``.

        EXAMPLES::

            sage: PF = WeylGroup(['C',3,1]).pieri_factors()
            sage: PF.generating_series()
            6*z^6 + 14*z^5 + 18*z^4 + 15*z^3 + 9*z^2 + 4*z + 1

            sage: PF = WeylGroup(['B',4]).pieri_factors()
            sage: PF.generating_series()
            z^7 + 6*z^6 + 14*z^5 + 18*z^4 + 15*z^3 + 9*z^2 + 4*z + 1
        """
        if weight is None:
            weight = self.default_weight()

        return sum(weight(w.length()) for w in self)

    @cached_method
    def default_weight(self):
        r"""
        Return the function `i\mapsto z^i`, where `z` is the
        generator of ``QQ['z']``.

        EXAMPLES::

            sage: W = WeylGroup(["A", 3, 1])
            sage: weight = W.pieri_factors().default_weight()
            sage: weight(1)
            z
            sage: weight(5)
            z^5

        TESTS::

            sage: weight(4) in QQ['z']
            True
            sage: weight(0) in QQ['z']
            True
            sage: weight(0).parent() == QQ['z']  # todo: not implemented
            True
        """
        R = QQ['z']
        z = R.gen()
        return lambda i: z**i

    def _test_maximal_elements(self, **options):
        r"""
        Check that the conjectural type-free definition of Pieri
        factors matches with the proven type-specific definition.

        .. SEEALSO:: :class:`TestSuite`.

        EXAMPLES::

            sage: W = WeylGroup(['A',4,1])
            sage: PF = W.pieri_factors()
            sage: PF._test_maximal_elements()
            sage: WeylGroup(['B',5]).pieri_factors()._test_maximal_elements()

        TESTS::

            sage: W = WeylGroup(['C',4,1])
            sage: PF = W.pieri_factors()
            sage: PF._test_maximal_elements()
            sage: WeylGroup(['D',5,1]).pieri_factors()._test_maximal_elements()
            sage: WeylGroup(['A',5,1]).pieri_factors()._test_maximal_elements()
            sage: WeylGroup(['B',5,1]).pieri_factors()._test_maximal_elements()
        """
        tester = self._tester(**options)
        tester.assertEqual(set(self.maximal_elements()),
                           set(self.maximal_elements_combinatorial()))

    @cached_method
    def max_length(self):
        r"""
        Return the maximal length of a Pieri factor.

        EXAMPLES:

        In type A and A affine, this is `n`::

            sage: WeylGroup(['A',5]).pieri_factors().max_length()
            5
            sage: WeylGroup(['A',5,1]).pieri_factors().max_length()
            5

        In type B and B affine, this is `2n-1`::

            sage: WeylGroup(['B',5,1]).pieri_factors().max_length()
            9
            sage: WeylGroup(['B',5]).pieri_factors().max_length()
            9

        In type C affine this is `2n`::

            sage: WeylGroup(['C',5,1]).pieri_factors().max_length()
            10

        In type D affine this is `2n-2`::

            sage: WeylGroup(['D',5,1]).pieri_factors().max_length()
            8
        """
        return self.maximal_elements()[0].length()


class PieriFactors_finite_type(PieriFactors):
    r"""
    The Pieri factors of finite type A are the restriction of the
    Pieri factors of affine type A to finite permutations (under the
    canonical embedding of finite type A into the affine Weyl group),
    and the Pieri factors of finite type B are the restriction of the
    Pieri factors of affine type C. The finite type D Pieri factors
    are (weakly) conjectured to be the restriction of the Pieri
    factors of affine type D.
    """

    def maximal_elements(self):
        r"""
        The current algorithm uses the fact that the maximal Pieri factors
        of affine type A,B,C, or D either contain a finite Weyl group
        element, or contain an affine Weyl group element whose reflection
        by `s_0` gets a finite Weyl group element, and that either of
        these finite group elements will serve as a maximal element for
        finite Pieri factors. A better algorithm is desirable.

        EXAMPLES::

            sage: PF = WeylGroup(['A',5]).pieri_factors()
            sage: [v.reduced_word() for v in PF.maximal_elements()]
            [[5, 4, 3, 2, 1]]

            sage: WeylGroup(['B',4]).pieri_factors().maximal_elements()
            [
            [-1  0  0  0]
            [ 0  1  0  0]
            [ 0  0  1  0]
            [ 0  0  0  1]
            ]
        """
        ct = self.W.cartan_type()

        # The following line may need to be changed when generalizing to more than types A and B.
        if ct.type() != 'A' and ct.type() != 'B':
            raise NotImplementedError("currently only implemented for finite types A and B")

        ct_aff = ct.dual().affine()

        max_elts_affine = WeylGroup(ct_aff).pieri_factors().maximal_elements()

        for w in max_elts_affine:
            if 0 not in w.reduced_word():
                return [self.W.from_reduced_word(w.reduced_word())]
        for w in max_elts_affine:
            if 0 not in w.apply_simple_reflection(0).reduced_word():
                return [self.W.from_reduced_word(w.apply_simple_reflection(0).reduced_word())]


class PieriFactors_affine_type(PieriFactors):

    def maximal_elements(self):
        r"""
        Return the maximal elements of ``self`` with respect to Bruhat order.

        The current implementation is via a conjectural type-free
        formula. Use :meth:`maximal_elements_combinatorial` for proven
        type-specific implementations. To compare type-free and
        type-specific (combinatorial) implementations, use method
        :meth:`_test_maximal_elements`.

        EXAMPLES::

            sage: W = WeylGroup(['A',4,1])
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 4, 3, 2], [1, 0, 4, 3], [2, 1, 0, 4], [3, 2, 1, 0], [4, 3, 2, 1]]

            sage: W = WeylGroup(RootSystem(["C",3,1]).weight_space())
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 1, 2, 3, 2, 1], [1, 0, 1, 2, 3, 2], [1, 2, 3, 2, 1, 0],
             [2, 1, 0, 1, 2, 3], [2, 3, 2, 1, 0, 1], [3, 2, 1, 0, 1, 2]]

            sage: W = WeylGroup(RootSystem(["B",3,1]).weight_space())
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 2, 3, 2, 0], [1, 0, 2, 3, 2], [1, 2, 3, 2, 1],
             [2, 1, 0, 2, 3], [2, 3, 2, 1, 0], [3, 2, 1, 0, 2]]

            sage: W = WeylGroup(['D',4,1])
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 2, 4, 3, 2, 0], [1, 0, 2, 4, 3, 2], [1, 2, 4, 3, 2, 1],
             [2, 1, 0, 2, 4, 3], [2, 4, 3, 2, 1, 0], [3, 2, 1, 0, 2, 3],
             [4, 2, 1, 0, 2, 4], [4, 3, 2, 1, 0, 2]]
        """
        ct = self.W.cartan_type()
        s = ct.translation_factors()[1]
        R = RootSystem(ct).weight_space()
        Lambda = R.fundamental_weights()
        orbit = [R.reduced_word_of_translation(x)
                 for x in (s*(Lambda[1]-Lambda[1].level()*Lambda[0]))._orbit_iter()]
        return [self.W.from_reduced_word(x) for x in orbit]


class PieriFactors_type_A(PieriFactors_finite_type):
    r"""
    The set of Pieri factors for finite type A.

    This is the set of elements of the Weyl group that have a reduced
    word that is strictly decreasing. This may also be viewed as the
    restriction of affine type A Pieri factors to finite Weyl group
    elements.
    """

    def __init__(self, W):
        r"""
        EXAMPLES::

            sage: PF = WeylGroup(['A',5]).pieri_factors()
            sage: PF
            Pieri factors for Weyl Group of type ['A', 5] (as a matrix group acting on the ambient space)

        TESTS::

            sage: PF = WeylGroup(['A',3]).pieri_factors()
            sage: PF.__class__
            <class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_A_with_category'>
            sage: TestSuite(PF).run()
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())
        self.W = W

    def maximal_elements_combinatorial(self):
        r"""
        Return the maximal Pieri factors, using the type A
        combinatorial description.

        EXAMPLES::

            sage: W = WeylGroup(['A',4])
            sage: PF = W.pieri_factors()
            sage: PF.maximal_elements_combinatorial()[0].reduced_word()
            [4, 3, 2, 1]
        """
        return [self.W.from_reduced_word(range(self.W.cartan_type().n, 0, -1))]

    def stanley_symm_poly_weight(self,w):
        r"""
        EXAMPLES::

            sage: W = WeylGroup(['A',4])
            sage: PF = W.pieri_factors()
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([3,1]))
            0
        """
        return 0


class PieriFactors_type_B(PieriFactors_finite_type):
    r"""
    The type B finite Pieri factors are realized as the set of
    elements that have a reduced word that is a subword of
    `12...(n-1)n(n-1)...21`. They are the restriction of the type C
    affine Pieri factors to the set of finite Weyl group elements
    under the usual embedding.
    """

    def __init__(self, W):
        r"""
        EXAMPLES::

            sage: WeylGroup(['B',5]).pieri_factors()
            Pieri factors for Weyl Group of type ['B', 5] (as a matrix group acting on the ambient space)

        TESTS::

            sage: PF = WeylGroup(['B',3]).pieri_factors()
            sage: PF.__class__
            <class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_B_with_category'>
            sage: TestSuite(PF).run()
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())
        self.W = W

    def maximal_elements_combinatorial(self):
        r"""
        Return the maximal Pieri factors, using the type B
        combinatorial description.

        EXAMPLES::

            sage: PF = WeylGroup(['B',4]).pieri_factors()
            sage: PF.maximal_elements_combinatorial()[0].reduced_word()
            [1, 2, 3, 4, 3, 2, 1]
        """
        N = self.W.cartan_type().n
        li = list(range(1, N)) + list(range(N, 0, -1))
        return [self.W.from_reduced_word(li)]

    def stanley_symm_poly_weight(self, w):
        r"""
        Weight used in computing Stanley symmetric polynomials of type `B`.

        The weight for finite type B is the number of components
        of the support of an element minus the number of occurrences
        of `n` in a reduced word.

        EXAMPLES::

            sage: W = WeylGroup(['B',5])
            sage: PF = W.pieri_factors()
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([3,1,5]))
            2
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([3,4,5]))
            0
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([1,2,3,4,5,4]))
            0
        """
        r = w.reduced_word().count(self.W.n)
        return WeylGroup(self.W.cartan_type().dual().affine()).pieri_factors().stanley_symm_poly_weight(w) - r


class PieriFactors_type_A_affine(PieriFactors_affine_type):
    r"""
    The set of Pieri factors for type A affine, that is the set of
    elements of the Weyl Group which are cyclically decreasing.

    Those are used for constructing (affine) Stanley symmetric functions.

    The Pieri factors are in bijection with the proper subsets of the
    ``index_set``. The bijection is given by the support. Namely, let `f`
    be a Pieri factor, and `red` a reduced word for `f`.  No simple
    reflection appears twice in red, and the support `S` of `red`
    (that is the `i` such that `s_i` appears in `red`) does not depend
    on the reduced word).
    """

    @staticmethod
    def __classcall__(cls, W, min_length=0, max_length=infinity,
                      min_support=frozenset([]), max_support=None):
        r"""
        TESTS::

            sage: W = WeylGroup(['A',5,1])
            sage: PF1 = sage.combinat.root_system.pieri_factors.PieriFactors_type_A_affine(W)
            sage: PF2 = W.pieri_factors()
            sage: PF3 = W.pieri_factors(min_support = [])
            sage: PF4 = W.pieri_factors(max_support = [0,1,2,3,4,5])
            sage: PF5 = W.pieri_factors(max_length = 10)
            sage: PF6 = W.pieri_factors(min_length = 0)
            sage: PF2 is PF1, PF3 is PF1, PF4 is PF1, PF5 is PF1, PF6 is PF1
            (True, True, True, True, True)
        """
        assert W.cartan_type().is_affine() and W.cartan_type().letter == 'A'

        # We use Python's frozenset's rather that Sage's Set's because
        # the latter do not yet support the issubset method
        min_support = frozenset(min_support)
        if max_support is None:
            max_support = frozenset(W.index_set())
        else:
            max_support = frozenset(max_support)
        min_length = max(min_length, len(min_support))
        max_length = min(len(max_support), max_length, len(W.index_set()) - 1)
        return super().__classcall__(cls, W, min_length, max_length, min_support, max_support)

    def __init__(self, W, min_length, max_length, min_support, max_support):
        r"""
        INPUT:

         - ``W`` -- a Weyl group of affine type `A`
         - ``min_length``, ``max_length`` -- non negative integers
         - ``min_support``, ``max_support`` -- subsets of the index set of `W`

        EXAMPLES::

            sage: PF = WeylGroup(["A", 3, 1]).pieri_factors(); PF
            Pieri factors for Weyl Group of type ['A', 3, 1] (as a matrix group acting on the root space)

        TESTS::

            sage: PF = WeylGroup(['A',3,1]).pieri_factors()
            sage: PF.__class__
            <class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_A_affine_with_category'>
            sage: TestSuite(PF).run()

            sage: PF = WeylGroup(['A',3,1]).pieri_factors(min_length = 3)
            sage: [w.reduced_word() for w in PF]
            [[2, 1, 0], [1, 0, 3], [0, 3, 2], [3, 2, 1]]

            sage: PF = WeylGroup(['A',4,1]).pieri_factors(min_support = [0,2])
            sage: [w.reduced_word() for w in PF]
            [[2, 0], [2, 1, 0], [3, 2, 0], [0, 4, 2], [3, 2, 1, 0], [2, 1, 0, 4], [0, 4, 3, 2]]

            sage: PF = WeylGroup(['A',5,1]).pieri_factors(min_support = [0,1,2], max_support = [0,1,2,3])
            sage: [w.reduced_word() for w in PF]
            [[2, 1, 0], [3, 2, 1, 0]]

            sage: PF = WeylGroup(['A',5,1]).pieri_factors(min_length = 2, max_length = 5)
            sage: PF.generating_series()
            6*z^5 + 15*z^4 + 20*z^3 + 15*z^2
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())
        self.W = W

        self._min_support = frozenset(min_support)
        self._max_support = frozenset(max_support)

        if not self._min_support.issubset(self._max_support):
            raise ValueError("the min support must be a subset "
                             "of the max support")

        self._extra_support = self._max_support.difference(self._min_support)

        self._min_length = min_length
        self._max_length = max_length

    def subset(self, length):
        r"""
        Return the subset of the elements of ``self`` of length ``length``.

        INPUT:

         - ``length`` -- a non-negative integer

        EXAMPLES::

            sage: PF = WeylGroup(["A", 3, 1]).pieri_factors(); PF
            Pieri factors for Weyl Group of type ['A', 3, 1] (as a matrix group acting on the root space)
            sage: PF3 = PF.subset(length = 2)
            sage: PF3.cardinality()
            6

        TESTS:

        We check that there is no reference effect (there was at some point!)::

            sage: PF.cardinality()
            15
        """
        return self.__class__(self.W,
                              min_support=self._min_support,
                              max_support=self._max_support,
                              min_length=length,
                              max_length=length)

    def maximal_elements_combinatorial(self):
        r"""
        Return the maximal Pieri factors, using the affine type A
        combinatorial description.

        EXAMPLES::

            sage: W = WeylGroup(['A',4,1])
            sage: PF = W.pieri_factors()
            sage: [w.reduced_word() for w in PF.maximal_elements_combinatorial()]
            [[3, 2, 1, 0], [2, 1, 0, 4], [1, 0, 4, 3], [0, 4, 3, 2], [4, 3, 2, 1]]
        """
        return self.subset(self._max_length)

    def _test_maximal_elements(self, **options):
        r"""
        Same as :meth:`PieriFactors._test_maximal_elements`, but skips
        the tests if ``self`` is not the full set of Pieri factors.

        EXAMPLES::

            sage: W = WeylGroup(['A',4,1])
            sage: W.pieri_factors()._test_maximal_elements(verbose = True)
            sage: W.pieri_factors(min_length = 1)._test_maximal_elements(verbose = True)
            Strict subset of the Pieri factors; skipping test

        """
        tester = self._tester(**options)
        index_set = self.W.index_set()
        if self._min_length > 0 or self._max_length < len(self.W.index_set())-1 or self._max_support != frozenset(index_set):
            tester.info("\n  Strict subset of the Pieri factors; skipping test")
            return
        return super()._test_maximal_elements(**options)

    def __contains__(self, w):
        r"""
        Return whether ``w`` is in ``self``.

        EXAMPLES::

            sage: W = WeylGroup(['A',6,1])
            sage: PF = W.pieri_factors()
            sage: w=W.from_reduced_word([4,3,1,0,6])
            sage: w in PF
            True
            sage: w=W.from_reduced_word([4,3,1,0,2])
            sage: w in PF
            False
            sage: w=W.from_reduced_word([4,3,1,0,6,0])
            sage: w in PF
            False
            sage: w=W.from_reduced_word([])
            sage: w in PF
            True
            sage: w=W.from_reduced_word([3,2,1,0])
            sage: w in PF
            True

            sage: W=WeylGroup(['A',3,1])
            sage: PF = W.pieri_factors()
            sage: w=W.from_reduced_word([3,2,1,0])
            sage: w in PF
            False
        """
        if w not in self.W:
            raise ValueError("{} is not an element of the Weyl group".format(w))
        n = len(self.W.index_set()) - 1
        red = w.reduced_word()
        support = set(red)

        if len(support) < len(red):  # There should be no repetitions
            return False

        if not (self._min_length <= len(support) and
               len(support) <= self._max_length and
               self._min_support.issubset(support) and
               support.issubset(self._max_support)):
            return False

        [rank, unrank] = sage.combinat.ranker.from_list(red)
        for i in red:
            j = (i + 1) % (n + 1)
            if j in support:
                if rank(i) < rank(j):
                    return False
        return True

    def __getitem__(self, support):
        r"""
        Return the cyclically decreasing element associated with ``support``.

        INPUT:

        - ``support`` -- a proper subset of the index_set, as a list or set

        EXAMPLES::

            sage: W = WeylGroup(["A", 5, 1])
            sage: W.pieri_factors()[[0,1,2,3,5]].reduced_word()
            [3, 2, 1, 0, 5]
            sage: W.pieri_factors()[[0,1,3,4,5]].reduced_word()
            [1, 0, 5, 4, 3]
            sage: W.pieri_factors()[[0,1,2,3,4]].reduced_word()
            [4, 3, 2, 1, 0]

        """
        index_set = sorted(self.W.index_set())
        support = sorted(support)
        if not set(support).issubset(set(index_set)) or support == index_set:
            raise ValueError("the support must be a proper subset of the index set")
        if not support:
            return self.W.one()
        s = self.W.simple_reflections()
        i = 0
        while i < len(support) and support[i] == index_set[i]:
            i += 1
        # This finds the first hole: either ley[i] is maximal or support[i] < support[i+1]+1
        return prod((s[j] for j in list(reversed(support[0:i])) + list(reversed(support[i:]))), self.W.one())

    def cardinality(self):
        r"""
        Return the cardinality of ``self``.

        EXAMPLES::

            sage: WeylGroup(["A", 3, 1]).pieri_factors().cardinality()
            15
        """
        if self._min_length == len(self._min_support) and self._max_length == len(self._max_support) - 1:
            return Integer(2**(len(self._extra_support)) - 1)
        else:
            return self.generating_series(weight=ConstantFunction(1))

    def generating_series(self, weight=None):
        r"""
        Return a length generating series for the elements of ``self``.

        EXAMPLES::

            sage: W = WeylGroup(["A", 3, 1])
            sage: W.pieri_factors().cardinality()
            15
            sage: W.pieri_factors().generating_series()
            4*z^3 + 6*z^2 + 4*z + 1
        """
        if weight is None:
            weight = self.default_weight()
        l_min = len(self._min_support)
        l_max = len(self._max_support)
        return sum(binomial(l_max - l_min, l - l_min) * weight(l)
                   for l in range(self._min_length, self._max_length + 1))

    def __iter__(self):
        r"""
        Return an iterator over the elements of ``self``.

        EXAMPLES::

            sage: W = WeylGroup(['A',4,1])
            sage: PF = W.pieri_factors()
            sage: f = PF.__iter__()
            sage: next(f)
            [1 0 0 0 0]
            [0 1 0 0 0]
            [0 0 1 0 0]
            [0 0 0 1 0]
            [0 0 0 0 1]
            sage: [next(f).reduced_word() for i in range(6)]
            [[0], [1], [2], [3], [4], [1, 0]]
        """
        from sage.combinat.subset import Subsets
        for l in range(self._min_length, self._max_length + 1):
            for extra in Subsets(self._extra_support,
                                 l - len(self._min_support)):
                yield self[self._min_support.union(extra)]

    def stanley_symm_poly_weight(self, w):
        r"""
        Weight used in computing (affine) Stanley symmetric polynomials
        for affine type A.

        EXAMPLES::

            sage: W = WeylGroup(['A',5,1])
            sage: PF = W.pieri_factors()
            sage: PF.stanley_symm_poly_weight(W.one())
            0
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,4,2,1,0]))
            0
        """
        return 0


class PieriFactors_type_C_affine(PieriFactors_affine_type):
    r"""
    The type C affine Pieri factors are realized as the order ideal (in Bruhat
    order) generated by cyclic rotations of the element with unique reduced word
    `123...(n-1)n(n-1)...3210`.

    EXAMPLES::

        sage: W = WeylGroup(['C',3,1])
        sage: PF = W.pieri_factors()
        sage: sorted([u.reduced_word() for u in PF.maximal_elements()], key=str)
        [[0, 1, 2, 3, 2, 1], [1, 0, 1, 2, 3, 2], [1, 2, 3, 2, 1, 0],
         [2, 1, 0, 1, 2, 3], [2, 3, 2, 1, 0, 1], [3, 2, 1, 0, 1, 2]]
    """

    def __init__(self, W):
        r"""
        TESTS::

            sage: PF = WeylGroup(['C',3,1]).pieri_factors()
            sage: PF.__class__
            <class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_C_affine_with_category'>
            sage: TestSuite(PF).run()  # long time (4s on sage.math, 2011)
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())
        self.W = W

    @cached_method
    def maximal_elements_combinatorial(self):
        r"""
        Return the maximal Pieri factors, using the affine type C
        combinatorial description.

        EXAMPLES::

            sage: PF = WeylGroup(['C',3,1]).pieri_factors()
            sage: [w.reduced_word() for w in PF.maximal_elements_combinatorial()]
            [[0, 1, 2, 3, 2, 1], [1, 0, 1, 2, 3, 2], [2, 1, 0, 1, 2, 3], [3, 2, 1, 0, 1, 2], [2, 3, 2, 1, 0, 1], [1, 2, 3, 2, 1, 0]]
        """
        n = self.W.n
        rho = self.W.from_reduced_word(range(1, n-1))*self.W.from_reduced_word(range(n-1,-1,-1))
        rotations = []
        for i in range(2 * (n - 1)):
            rho = rho.apply_simple_reflections(rho.descents()).apply_simple_reflections(rho.descents(), side='left')
            rotations.append(rho)
        return rotations

    def stanley_symm_poly_weight(self, w):
        r"""
        Return the weight of a Pieri factor to be used in the definition of
        Stanley symmetric functions.

        For type C, this weight is the number of connected components
        of the support (the indices appearing in a reduced word) of an
        element.

        EXAMPLES::

            sage: W = WeylGroup(['C',5,1])
            sage: PF = W.pieri_factors()
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([1,3]))
            2
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([1,3,2,0]))
            1
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,3,0]))
            3
            sage: PF.stanley_symm_poly_weight(W.one())
            0
        """
        # The algorithm="delete" is a workaround when the set of
        # vertices is empty, in which case subgraph tries another
        # method which turns out to currently fail with Dynkin diagrams
        return DiGraph(DynkinDiagram(w.parent().cartan_type())).subgraph(set(w.reduced_word()), algorithm="delete").connected_components_number()


class PieriFactors_type_B_affine(PieriFactors_affine_type):
    r"""
    The type B affine Pieri factors are realized as the order ideal (in Bruhat
    order) generated by the following elements:

    - cyclic rotations of the element with reduced word
      `234...(n-1)n(n-1)...3210`,
      except for `123...n...320` and `023...n...321`.
    - `123...(n-1)n(n-1)...321`
    - `023...(n-1)n(n-1)...320`

    EXAMPLES::

        sage: W = WeylGroup(['B',4,1])
        sage: PF = W.pieri_factors()
        sage: W.from_reduced_word([2,3,4,3,2,1,0]) in PF.maximal_elements()
        True
        sage: W.from_reduced_word([0,2,3,4,3,2,1]) in PF.maximal_elements()
        False
        sage: W.from_reduced_word([1,0,2,3,4,3,2]) in PF.maximal_elements()
        True
        sage: W.from_reduced_word([0,2,3,4,3,2,0]) in PF.maximal_elements()
        True
        sage: W.from_reduced_word([0,2,0]) in PF
        True
    """

    def __init__(self, W):
        r"""

        TESTS::

            sage: PF = WeylGroup(["B",3,1]).pieri_factors()
            sage: PF.__class__
            <class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_B_affine_with_category'>
            sage: TestSuite(PF).run()
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())
        self.W = W

    @cached_method
    def maximal_elements_combinatorial(self):
        r"""
        Return the maximal Pieri factors, using the affine type B
        combinatorial description.

        EXAMPLES::

            sage: W = WeylGroup(['B',4,1])
            sage: [u.reduced_word() for u in W.pieri_factors().maximal_elements_combinatorial()]
            [[1, 0, 2, 3, 4, 3, 2], [2, 1, 0, 2, 3, 4, 3], [3, 2, 1, 0, 2, 3, 4], [4, 3, 2, 1, 0, 2, 3], [3, 4, 3, 2, 1, 0, 2], [2, 3, 4, 3, 2, 1, 0], [1, 2, 3, 4, 3, 2, 1], [0, 2, 3, 4, 3, 2, 0]]
        """
        n = self.W.n
        rho = self.W.from_reduced_word(range(2,n-1))*self.W.from_reduced_word(range(n-1,-1,-1))
        rotations = []
        for i in range(2 * (n - 2)):
            rho = rho.apply_simple_reflections(rho.descents()).apply_simple_reflections(rho.descents(), side='left')
            rotations.append(rho)
        rotations.append(self.W.from_reduced_word(range(1,n-1))*self.W.from_reduced_word(range(n-1,0,-1)))
        rotations.append(self.W.from_reduced_word([0])*self.W.from_reduced_word(range(2,n-1))*self.W.from_reduced_word(range(n-1,1,-1))*self.W.from_reduced_word([0]))
        return rotations

    def stanley_symm_poly_weight(self, w):
        r"""
        Return the weight of a Pieri factor to be used in the definition of
        Stanley symmetric functions.

        For type B, this weight involves the number of components of
        the complement of the support of an element, where we consider
        0 and 1 to be one node -- if 1 is in the support, then we
        pretend 0 in the support, and vice versa.  We also consider 0
        and 1 to be one node for the purpose of counting components of
        the complement (as if the Dynkin diagram were that of type C).
        Let n be the rank of the affine Weyl group in question (if
        type ``['B',k,1]`` then we have n = k+1).  Let ``chi(v.length() < n-1)``
        be the indicator function that is 1 if the length of v is
        smaller than n-1, and 0 if the length of v is greater than or
        equal to n-1.  If we call ``c'(v)`` the number of components of
        the complement of the support of v, then the type B weight is
        given by ``weight = c'(v) - chi(v.length() < n-1)``.

        EXAMPLES::

            sage: W = WeylGroup(['B',5,1])
            sage: PF = W.pieri_factors()
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([0,3]))
            1
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([0,1,3]))
            1
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,3]))
            1
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,3,4,5]))
            0
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([0,5]))
            0
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,4,5,4,3,0]))
            -1
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([4,5,4,3,0]))
            0
        """
        ct = w.parent().cartan_type()
        support = set(w.reduced_word())
        if 1 in support or 0 in support:
            support_complement = set(ct.index_set()).difference(support).difference(set([0, 1]))
        else:
            support_complement = set(ct.index_set()).difference(support).difference(set([0]))
        return DiGraph(DynkinDiagram(ct)).subgraph(support_complement, algorithm="delete").connected_components_number() - 1


class PieriFactors_type_D_affine(PieriFactors_affine_type):
    r"""
    The type D affine Pieri factors are realized as the order ideal
    (in Bruhat order) generated by the following elements:

     * cyclic rotations of the element with reduced word
       `234...(n-2)n(n-1)(n-2)...3210`
       such that 1 and 0 are always adjacent and (n-1) and n are always adjacent.
     * `123...(n-2)n(n-1)(n-2)...321`
     * `023...(n-2)n(n-1)(n-2)...320`
     * `n(n-2)...2102...(n-2)n`
     * `(n-1)(n-2)...2102...(n-2)(n-1)`

    EXAMPLES::

        sage: W = WeylGroup(['D',5,1])
        sage: PF = W.pieri_factors()
        sage: W.from_reduced_word([3,2,1,0]) in PF
        True
        sage: W.from_reduced_word([0,3,2,1]) in PF
        False
        sage: W.from_reduced_word([0,1,3,2]) in PF
        True
        sage: W.from_reduced_word([2,0,1,3]) in PF
        True
        sage: sorted([u.reduced_word() for u in PF.maximal_elements()], key=str)
        [[0, 2, 3, 5, 4, 3, 2, 0], [1, 0, 2, 3, 5, 4, 3, 2], [1, 2, 3, 5, 4, 3, 2, 1],
         [2, 1, 0, 2, 3, 5, 4, 3], [2, 3, 5, 4, 3, 2, 1, 0], [3, 2, 1, 0, 2, 3, 5, 4],
         [3, 5, 4, 3, 2, 1, 0, 2], [4, 3, 2, 1, 0, 2, 3, 4], [5, 3, 2, 1, 0, 2, 3, 5],
         [5, 4, 3, 2, 1, 0, 2, 3]]
    """

    def __init__(self, W):
        r"""
        TESTS::

            sage: PF = WeylGroup(["D",4,1]).pieri_factors()
            sage: PF.__class__
            <class 'sage.combinat.root_system.pieri_factors.PieriFactors_type_D_affine_with_category'>
            sage: TestSuite(PF).run()  # long time
        """
        Parent.__init__(self, category=FiniteEnumeratedSets())
        self.W = W

    @cached_method
    def maximal_elements_combinatorial(self):
        r"""
        Return the maximal Pieri factors, using the affine type D
        combinatorial description.

        EXAMPLES::

            sage: W = WeylGroup(['D',5,1])
            sage: PF = W.pieri_factors()
            sage: set(PF.maximal_elements_combinatorial()) == set(PF.maximal_elements())
            True
        """
        n = self.W.n
        rho = self.W.from_reduced_word(range(2,n))*self.W.from_reduced_word(range(n-3,-1,-1))
        rotations = []
        for i in range(2 * (n - 3)):
            rho = rho.apply_simple_reflections(rho.descents()).apply_simple_reflections(rho.descents(),side='left')
            rotations.append(rho)

        rotations.append(self.W.from_reduced_word(range(1,n))*self.W.from_reduced_word(range(n-3,0,-1)))
        rotations.append(self.W.from_reduced_word([0])*self.W.from_reduced_word(range(2,n))*self.W.from_reduced_word(range(n-3,1,-1))*self.W.from_reduced_word([0]))
        rotations.append(self.W.from_reduced_word(range(n-2,-1,-1))*self.W.from_reduced_word(range(2,n-1)))
        rotations.append(self.W.from_reduced_word([n-1])*self.W.from_reduced_word(range(n-3,-1,-1))*self.W.from_reduced_word(range(2,n-2))*self.W.from_reduced_word([n-1]))
        return rotations

    def stanley_symm_poly_weight(self, w):
        r"""
        Return the weight of `w`, to be used in the definition of
        Stanley symmetric functions.

        INPUT:

        - ``w`` -- a Pieri factor for this type

        For type `D`, this weight involves
        the number of components of the complement of the support of
        an element, where we consider `0` and `1` to be one node -- if `1`
        is in the support, then we pretend `0` in the support, and vice
        versa.  Similarly with `n-1` and `n`.  We also consider `0` and
        `1`, `n-1` and `n` to be one node for the purpose of counting
        components of the complement (as if the Dynkin diagram were
        that of type `C`).

        Type D Stanley symmetric polynomial weights are still
        conjectural.  The given weight comes from conditions on
        elements of the affine Fomin-Stanley subalgebra, but work is
        needed to show this weight is correct for affine Stanley
        symmetric functions -- see [LSS2009, Pon2010]_ for details.

        EXAMPLES::

            sage: W = WeylGroup(['D', 5, 1])
            sage: PF = W.pieri_factors()
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,2,1]))
            0
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,2,1,0]))
            0
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([5,2]))
            1
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([]))
            0

            sage: W = WeylGroup(['D',7,1])
            sage: PF = W.pieri_factors()
            sage: PF.stanley_symm_poly_weight(W.from_reduced_word([2,4,6]))
            2
        """
        ct = w.parent().cartan_type()
        support = set(w.reduced_word())
        n = w.parent().n
        if 1 in support or 0 in support:
            support = support.union(set([1])).difference(set([0]))
        if n in support or n - 1 in support:
            support = support.union(set([n - 2])).difference(set([n - 1]))
        support_complement = set(range(1, n - 1)).difference(support)
        return DiGraph(DynkinDiagram(ct)).subgraph(support_complement).connected_components_number() - 1


# Inserts those classes in CartanTypes
from sage.combinat.root_system import type_A_affine, type_B_affine, type_C_affine, type_D_affine, type_A, type_B
type_A_affine.CartanType.PieriFactors = PieriFactors_type_A_affine
type_B_affine.CartanType.PieriFactors = PieriFactors_type_B_affine
type_C_affine.CartanType.PieriFactors = PieriFactors_type_C_affine
type_D_affine.CartanType.PieriFactors = PieriFactors_type_D_affine
type_A.CartanType.PieriFactors = PieriFactors_type_A
type_B.CartanType.PieriFactors = PieriFactors_type_B

# Pieri factors for these types have not yet been mathematically
# introduced rigorously
#
# import type_C, type_D, type_E, type_F, type_G, type_E_affine, type_F_affine, type_G_affine
#type_C.CartanType.PieriFactors = PieriFactors_type_C
#type_D.CartanType.PieriFactors = PieriFactors_type_D
#type_E.CartanType.PieriFactors = PieriFactors_type_E
#type_F.CartanType.PieriFactors = PieriFactors_type_F
#type_G.CartanType.PieriFactors = PieriFactors_type_G
#type_E_affine.CartanType.PieriFactors = PieriFactors_type_E_affine
#type_F_affine.CartanType.PieriFactors = PieriFactors_type_F_affine
#type_G_affine.CartanType.PieriFactors = PieriFactors_type_G_affine
